﻿import com.gamemeal.physics.Point3;
/**
 * @author Colin
 */
class com.gamemeal.ai.KNearestNeighbor {
	private var PROJX:Number;
	private var PROJY:Number;

	private var n : Number;// This is the number of point expected to be tested
	private var projaxe;// Current projection axe
	private var compare:Number;// Number of compare made to find the nearest
	private var maxradius:Number;// Maximum radius of search in the array
	private var ndata:Number;// Number of data in the arrays
	private var dataPt:Array;// Point array
	private var xindex:Array;// Index for coordinates X (x is the index, y is the value)
	private var yindex : Array;// Index for coordinates Y (x is the index, y is the value)
	private var flags : Array;// Array of flags that indicate the validity of point (true or false)

	private var cindex : Array;// Pointer to current index
	private var cvalue : Number;// Current values for the search

	private var cind : Number;
	private var cp : Object;// Current point being tested
	private var kn : Object;
	private var points : Array;
	
	public function KNearestNeighbor(points:Array){
	    // Projection axes defines
	    this.PROJX = 1;
	    this.PROJY = 2;
	
		this.points = points;
	
		this.n = 20; // We expect to test 10 points... (this is arbitrary)
		// Copy the point vector into an array
		this.ndata = points.length;
		// We create the arrays
		this.dataPt = [];
		this.xindex = [];
		this.yindex = [];
		this.flags = [];
		// We initialise the data
		for(var i=0; i < this.ndata; i++)
		{
			this.dataPt[i] = points[i];
			//trace(this.dataPt[i].x);
			// Create a new point which will have
			// field x : the index of the original point in the array (data)
			// field y : the value of the projected point on the axe
			this.xindex[i] = new Point3(i, this.dataPt[i].x,0);
			this.yindex[i] = new Point3(i, this.dataPt[i].y,0);
			this.flags[i] = true;    // The point is valid
		}
		// Sort the index for axe X
		this.cindex = this.xindex;
		this.bubbleSort();
		// Sort the index for axe Y
		this.cindex = this.yindex;
		this.bubbleSort();
		this.compare = 0;
	}


	private function bubbleSort() {
		//trace(this.cindex[1].y);
		var ptmp;
		for (var i = this.ndata-1; i >= 0; i--)
		{
			for (var j = 0; j<i; j++)
			{
				if (this.cindex[j].y > this.cindex[j+1].y)
				{   // Swap the points
					ptmp = this.cindex[j];
					this.cindex[j] = this.cindex[j+1];
					this.cindex[j+1] = ptmp;
				}
			}
		}
	}
	
	public function getCompare() {
		return this.compare;
	}
	
	public function getMaxRadius() {
		return this.maxradius;
	}
	
	public function getProjectionAxe() {
		return this.projaxe;
	}
	
	public function dichoSearchIndex(value) {
		//trace(value)
		var inf, sup, centre;
		inf = 0;
		sup = this.ndata-1;
	
		// Check for obious case
		if(value <= this.cindex[inf].y) return inf;
		else if(value >= this.cindex[sup].y) return sup;
	
		// Search until we have at least two elements
		while(sup > inf)
		{
			centre = int((inf+sup)/2);
			if(this.cindex[centre].y == value) return centre;
			else if(this.cindex[centre].y < value) inf = centre+1;
			else sup = centre-1;
		}
		return inf;
	}
	
	public function resetFlags() {
		for(var i=0; i < this.ndata; i++) this.flags[i] = true;
	}
	
	public function setKN(k) {
		if(k > 0 && k < this.points.size()) this.kn = k;
	}
	
	public function getKN() {
		return this.kn;
	}
	
	
	public function findFirstNN(p) {
		var index1, index2, i,j;
		var sparse1, sparse2;
		var xdim, ydim;
		var s1,s2;
		// Compute the dimension of the pointset
		xdim = this.xindex[this.ndata-1].y - this.xindex[0].y;
		ydim = this.yindex[this.ndata-1].y - this.yindex[0].y;
	
		// Remember the point being tested
		this.cp = p;
	
		// Reset the flags
		this.resetFlags();
	
		// Find the point on the projected axes
		this.cindex = this.xindex;
		//trace(p.x)
		index1 = this.dichoSearchIndex(p.x);
		this.cindex = this.yindex;
		//trace(p.y)
		index2 = this.dichoSearchIndex(p.y);
	
	
		//trace("***")
		//trace(index1)
		//trace(index2)
		//trace("***")
	
		// Mesure the sparsity of axe X
		i = int(index1 - this.n/2);
		if(i < 0) i = 0;
		j = int(index1 + this.n/2);
		if(j >= this.ndata) j = this.ndata-1;
		sparse1 = this.xindex[j].y - this.xindex[i].y;
		// Normalize sparsity
		s1 = int(sparse1/xdim);
	
		// Mesure the sparsity of axe Y
		i = int(index2 - this.n/2);
		if(i < 0) i = 0;
		j = int(index2 + this.n/2);
		if(j >= this.ndata) j = this.ndata-1;
		sparse2 = this.yindex[j].y - this.yindex[i].y;
		// Normalise sparsity
		s2 = int(sparse2/ydim);
	
		if(s1 > s2)
		{   // We take the x axe
			this.cindex = this.xindex;
			this.cvalue = p.x;
			this.cind = index1;
			this.projaxe = this.PROJX;
		}
		else
		{   // We take the y axe
			this.cindex = this.yindex;
			this.cvalue = p.y;
			this.cind = index2;
			this.projaxe = this.PROJY;
		}
	
		// Init the number of compare
		this.compare = 0;
		this.maxradius = 0;
		return this.findNextNN();
	}
	
	public function findNextNN() {
		var mindist,dist;
		var mini;
		var i, il, ir;
	
		// Find the radius of the circle
		// cind is already at the left of the test point
		il = this.cind;
		// Find the closest next valid point
		while(this.flags[this.cindex[il].x] == false && il > 0) il--;
		if(this.flags[this.cindex[il].x] == true)
		{
			// Compute the distance
			mindist = this.computeDistance(this.cp, this.dataPt[this.cindex[il].x]);
			this.compare++;
		}
		else
			// Put something big no chance of having a distance bigger than that
			mindist = 500*500;
	
		// Here, we must verify if it's not the end already
		if(this.cind < this.ndata-1)
		{
			ir = this.cind+1;
			while(this.flags[this.cindex[ir].x] == false && ir < this.ndata-1) ir++;
			if(this.flags[this.cindex[ir].x] == true)
			{
				dist = this.computeDistance(this.cp, this.dataPt[this.cindex[ir].x]);
				this.compare++;
			}
			else dist = 500*500;
	
			if(mindist < dist)
			{
				this.maxradius = Math.sqrt(mindist);
				mini = il;
			}
			else
			{
				mini = ir;
				this.maxradius = Math.sqrt(dist);
				mindist = dist;
			}
		}
		else
		{
			mini = il;
			ir = this.ndata-1;
			this.maxradius = Math.sqrt(mindist);
		}
	
	
		// Search to the left of cind
		i = il-1;
		while(i > 0 && this.maxradius > Math.abs(this.cvalue-this.cindex[i].y))
		{
			if(this.flags[this.cindex[i].x] == true)
			{
				dist = computeDistance(this.cp, this.dataPt[this.cindex[i].x]);
				this.compare++;
				if(dist < mindist)
				{
					mindist = dist;
					mini=i;
				}
			}
			// Go to the left
			i--;
		}
	
		// Search to the right of cind
		i = ir+1;
		while(i < this.ndata && this.maxradius > Math.abs(this.cindex[i].y - this.cvalue))
		{
			if(this.flags[this.cindex[i].x] == true)
			{
				dist = this.computeDistance(this.cp, this.dataPt[this.cindex[i].x]);
				this.compare++;
				if(dist < mindist)
				{
					mindist = dist;
					mini=i;
				}
			}
			i++; // Go to the right
		}
	
		// Set the flag of the point found to false so that
		// we don't find it again for next search
		this.flags[this.cindex[mini].x] = false;
	
		// return the closest point
		return this.dataPt[this.cindex[mini].x];
	}
	
	public function findNearestNeighborCrude( p ) {
		var mindist,dist;
		var mini = 0;
		// Init compare
		this.compare = 0;
		mindist = this.computeDistance(p, this.dataPt[mini]);
		for(var i=0; i < this.ndata; i++)
		{
			dist = this.computeDistance(p, this.dataPt[i]);
			this.compare++;
			if(dist < mindist)
			{
				mini = i;
				mindist = dist;
			}
		}
		return this.dataPt[mini];
	}
	
	public function computeDistance(p1, p2) {
		var dx,dy;
		dx = p2.x - p1.x;
		dy = p2.y - p1.y;
		return (dx*dx + dy*dy);
	}
}